//
//  Problem1423.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/10.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1423. 可获得的最大点数 【数组】【数组滑动】【数组拼接】
 几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
 每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
 你的点数就是你拿到手中的所有卡牌的点数之和。
 给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

 示例 1：
     输入：cardPoints = [1,2,3,4,5,6,1], k = 3
     输出：12
     解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。
 示例 2：
     输入：cardPoints = [2,2,2], k = 2
     输出：4
     解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。
 示例 3：
     输入：cardPoints = [9,7,7,9,7,7,9], k = 7
     输出：55
     解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。
 示例 4：
     输入：cardPoints = [1,1000,1], k = 1
     输出：1
     解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。
 示例 5：
     输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
     输出：202
 提示：
     1 <= cardPoints.length <= 10^5
     1 <= cardPoints[i] <= 10^4
     1 <= k <= cardPoints.length
 */
@objcMembers class Problem1423: NSObject {
    func solution() {
        print(maxScoreHua([1,2,3,4,5,6,1], 3))
        print(maxScoreHua([2,2,2], 2))
        print(maxScoreHua([9,7,7,9,7,7,9], 7))
        print(maxScoreHua([1,1000,1], 1))
        print(maxScoreHua([1,79,80,1,1,1,200,1], 3))
        print(maxScoreHua([30,88,33,37,18,77,54,73,31,88,93,25,18,31,71,8,97,20,98,16,65,40,18,25,13,51,59], 26))
    }
    
    /*
     动态规划 😭超时了
     1: 创建一个数组dp[len][len][k]
     2: dp[i][j][k]: 数组i～j抽取k次的最大值
     3: dp[i][j][k] = max()
        3.1 拿左边 card[i] + dp[i+1][j][k-1]
        3.2 拿右边 card[j] + dp[i][j][k-1]
     */
    func maxScore(_ cardPoints: [Int], _ k: Int) -> Int {
        if cardPoints.count == 1 {      // 特例：只有一张卡牌
            return cardPoints[0]
        }
        if k == 1 {                     // 特例：只允许抽取1次
            return max(cardPoints.first ?? 0, cardPoints.last ?? 0)
        }
        if cardPoints.count <= k {
            return cardPoints.reduce(0) { (first, second) -> Int in
                return first + second
            }
        }
        
        var dp = Array(repeating: Array(repeating: Array(repeating: 0, count: k+1), count: cardPoints.count), count: cardPoints.count)
        
        
        return maxScoreDP(cardPoints, k, &dp, 0, cardPoints.count-1)
    }
    
    func maxScoreDP(_ cardPoints: [Int], _ k: Int, _ dp: inout [[[Int]]], _ start: Int, _ end: Int) -> Int {
        if start > end {
            return Int.min
        }
        
        if k == 1 {
            dp[start][end][k] = max(cardPoints[start], cardPoints[end])
            return dp[start][end][k]
        }
            
        dp[start][end][k] = max(dp[start][end][k], cardPoints[start] + maxScoreDP(cardPoints, k-1, &dp, start+1, end))
        dp[start][end][k] = max(dp[start][end][k], cardPoints[end] + maxScoreDP(cardPoints, k-1, &dp, start, end-1))
        
        return dp[start][end][k]
    }
    
    /*
     滑动：
     由于只能从开头和末尾拿 k 张卡牌，所以最后剩下的必然是连续的 n−k 张卡牌。
     我们可以通过求出剩余卡牌点数之和的最小值，来求出拿走卡牌点数之和的最大值。
     */
    func maxScoreHua(_ cardPoints: [Int], _ k: Int) -> Int {
        if cardPoints.count == 1 {      // 特例：只有一张卡牌
            return cardPoints[0]
        }
        if k == 1 {                     // 特例：只允许抽取1次
            return max(cardPoints.first ?? 0, cardPoints.last ?? 0)
        }
        if cardPoints.count <= k {
            return cardPoints.reduce(0) { (first, second) -> Int in
                return first + second
            }
        }
        
        var value = 0
        // [1, 2, 3, 4] 2
        for i in cardPoints.count-k..<cardPoints.count {
            value += cardPoints[i]
        }
        var lastValue = value

        for i in 0..<k {
//            print("add: \(i), delete\(cardPoints.count-k+i)")
            lastValue = lastValue + cardPoints[i] - cardPoints[cardPoints.count-k+i]
            value = max(value, lastValue)
            
        }
        
        
        return value
    }
}
